package algorithm.leetcode.I1to100;


/**
 * 还是用第k小的数字 这个思路比较简单
 */

public class Q4 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int first = (nums1.length + nums2.length + 1) >> 1;
        int second = (nums1.length + nums2.length + 2) >> 1;

        return (getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, first)
                + getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, second)) * 0.5;
    }


    /**
     * 更一般的情况 A[1] ，A[2] ，A[3]，A[k/2] ... ，B[1]，B[2]，B[3]，B[k/2] ... ，如果 A[k/2]<B[k/2] ，那么A[1]，A[2]，A[3]，A[k/2]都不可能是第 k 小的数字。
     * @param nums1
     * @param start1
     * @param end1
     * @param nums2
     * @param start2
     * @param end2
     * @param k
     * @return
     */
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);

        // 几个base case,包含了一边长度为0的情况
        if (len1 == 0) return nums2[start2 + k - 1];
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 向下递归
        int i = Math.min(end1, start1+k/2-1);
        int j = Math.min(end2, start2+k/2-1);

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }


    public static void main(String[] args) {
        Q4 q4 = new Q4();
        int[] nums1 = {};
        int[] nums2 = {3, 4};
        System.out.println(q4.findMedianSortedArrays(nums1, nums2));
    }

}
